package week_plan;

import java.lang.reflect.Array;

public class MaxGap {
    /**
     * 一个无序数组 排序后的相连数最大差值是什么  arr里面是long类型  可正可负  时间复杂度O（n）
     *
     *
     * n个数  有n+1个桶  中间一定有一个空桶  这个空桶的作用就是来排除 最大值减去最小在一个桶的情况
     * 但是这个不一定是最大差值
     */
     public static int maxGap(int[] arr){
         if (arr == null || arr.length<2){
             return 0;
         }
         //数组长度
         int len = arr.length;
         //数组最小值最大值
         int min = Integer.MAX_VALUE;
         int max = Integer.MIN_VALUE;
         //遍历找到最大值最小值
         for (int i = 0 ;i<len;i++){
             min = Math.min(min,arr[i]);
             max = Math.max(max,arr[i]);
         }
         //只有一个数
         if (min == max){
             return 0;
         }
         //判断是否进来过数
         boolean[] hasNum = new boolean[len+1];
         int[] maxs = new int[len+1];
         int[] mins = new int[len+1];
         //桶号
         int bid = 0;
         for (int i =0;i<len;i++){
             bid=bucket(arr[i],len,max,min);
             //获取每个桶里面的最大值最小值
             mins[bid] = hasNum[bid] ? Math.min(mins[bid],arr[i]):arr[i];
             maxs[bid] = hasNum[bid] ? Math.max(maxs[bid],arr[i]):arr[i];
             hasNum[bid] =true;
         }
         int res = 0;
         int lastMax = 0;
         for (int i=0;i<len;i++){
             if (hasNum[i]){
                 res=Math.max(res,arr[i]-lastMax);
                 //更新这个桶的最大值
                 lastMax = maxs[i];
             }
         }
         return res;
     }
     //判断数字进几号桶
     public static int bucket(long arr,long len,long min,long max){
         return (int) ((arr-min)*len/(max-min));
     }
     public static void main(String[] args){
         int[] arr = {0,69,11,12,45,47};
         int i = maxGap(arr);
         System.out.println(i);
     }
}
